##from __future__ import with_statement
##from contextlib import contextmanager
##from random import randint
##
##from ..support import Namespace, State, logger
##
##class Variable(object):
##    """Decision variable used for CSPs and optimization problems."""
##    def __init__(self, name, domain=None, setter=None):
##        self.name = name
##        self.domain = domain
##        self.set = setter
##        
##    def __str__(self):
##        return "%s(%s in %s)" % (self.__class__.__name__, self.name, self.domain)
##        
##    def setter(self, fnc):
##        """Function decorator to set this variable's setter. Example:
##            @problem.variables.x.setter
##            def set_x(model, value):
##                model.find("foo.bar").config.stuff = value"""
##        self.set = fnc
##        return fnc
##        
##class Domain(list):
##    """Class implementing ordered and unordered finite discrete domains. 
##    Ordered domais take advantage of increased domain reduction by inequality
##    constraints like a < b, if b = 4 and the domain of a is [0..10], all values
##    that are >= 4 are removed at once."""
##    def __init__(self, values, cmp=None):
##        list.__init__(self, values)
##        self.__hidden = []
##        self.__cmp = cmp
##        if self.sortable():
##            self.sort()
##            
##    def copy(self):
##        clone = Domain(self)
##        clone.__hidden = [list(h) for h in self.__hidden]
##        clone.__cmp = self.__cmp
##        return clone
##        
##    def sortable(self):
##        return self.__cmp is not None
##        
##    def sort(self):
##        list.sort(self, cmp=self.__cmp)
##        
##    def push_state(self):
##        """Save current domain state. Variables hidden after pushing the state
##        are restored when the state is popped from the hidden stack."""
##        self.__hidden.append([])
##        
##    def pop_state(self):
##        """Restore domain state from the top of the stack. Variables 
##        hidden since the last push_state() are then available again."""
##        self.extend(self.__hidden.pop())
##        if self.sortable():
##            self.sort()
##            
##    def reset_state(self):
##        """Reset to the original domain state, including all possible values."""
##        for h in self.__hidden:
##            self.extend(h)
##        del self.__hidden[:]
##        if len(self) == 0:
##            raise ValueError("empty domain")
##        if self.sortable():
##            self.sort()
##            
##    def remove_ne(self, value):
##        pos = self.index(value)
##        del self[pos+1:]
##        del self[:pos]
##        
##    def remove_gt(self, value):
##        pos = self.index(value) + 1
##        del self[pos:]
##        
##    def remove_ge(self, value):
##        pos = self.index(value)
##        del self[pos:]
##        
##    def remove_lt(self, value):
##        pos = self.index(value)
##        del self[:pos]
##        
##    def remove_le(self, value):
##        pos = self.index(value) + 1
##        del self[:pos]
##        
##    def remove_in(self, values):
##        values = set(values)
##        kept = []
##        for value in self:
##            if value not in values:
##                kept.append(value)
##        self[:] = kept
##        
##    def remove_notin(self, values):
##        values = set(values)
##        kept = []
##        for value in self:
##            if value in values:
##                kept.append(value)
##        self[:] = kept
##        
##    def hide(self, value):
##        """Hide the given value from the domain. After that call the given 
##        value won't be seen as a possible value on that domain anymore. 
##        The hidden value will be restored when the previous saved state 
##        is popped."""
##        self.remove(value)
##        self.__hidden[-1].append(value)
##        
##    def hide_ne(self, value):
##        pos = self.index(value)
##        self.__hidden[-1].extend(self[pos+1:])
##        self.__hidden[-1].extend(self[:pos])
##        del self[pos+1:]
##        del self[:pos]
##        
##    def hide_gt(self, value):
##        pos = self.index(value) + 1
##        self.__hidden[-1].extend(self[pos:])
##        del self[pos:]
##        
##    def hide_ge(self, value):
##        pos = self.index(value)
##        self.__hidden[-1].extend(self[pos:])
##        del self[pos:]
##        
##    def hide_lt(self, value):
##        pos = self.index(value)
##        self.__hidden[-1].extend(self[:pos])
##        del self[:pos]
##        
##    def hide_le(self, value):
##        pos = self.index(value) + 1
##        self.__hidden[-1].extend(self[:pos])
##        del self[:pos]
##        
##    def hide_in(self, values):
##        values = set(values)
##        left = []
##        hidden = []
##        for value in self:
##            if value in values:
##                hidden.append(value)
##            else:
##                left.append(value)
##        self[:] = left
##        self.__hidden[-1].extend(hidden)
##        
##    def hide_notin(self, values):
##        values = set(values)
##        left = []
##        hidden = []
##        for value in self:
##            if value in values:
##                left.append(value)
##            else:
##                hidden.append(value)
##        self[:] = left
##        self.__hidden[-1].extend(hidden)
##        
##class Problem(object):
##    def __init__(self, solver=None):
##        self.variables = Namespace() # map {varname->varobj}
##        self.scope = dict() # map {constraint->scope}
##        self.solver = solver or ConstraintSolver()
##        
##    def __str__(self):
##        lines = [object.__repr__(self), "Variables"]
##        for var, varobj in sorted(self.variables.iteritems()):
##            lines.append("\t%s" % (varobj,))
##        lines.append("Constraints")
##        for constraint, scope in self.scope.iteritems():
##            lines.append("\t%s using %s" % (constraint, "ALL" if scope is None else scope))
##        return "\n".join(lines)
##        
##    def add_variable(self, var, domain=None):
##        if not isinstance(var, Variable):
##            var = Variable(var, domain)
##        elif var.domain is None:
##            var.domain = domain
##        if var.name in self.variables:
##            raise NameError("duplicate variable '%s'" % (var.name,))
##        self.variables[var.name] = var
##        
##    def add_variables(self, vars, domain=None):
##        for var in vars:
##            self.add_variable(var, domain)
##            
##    def add_constraint(self, constraint, scope=None):
##        if not isinstance(constraint, Constraint):
##            if callable(constraint):
##                constraint = FunctionConstraint(constraint)
##            else:
##                raise TypeError("expected callable or Constraint")
##        self.scope[constraint] = scope
##        
##    def add_constraints(self, constraints, scope=None):
##        """Add one or more constraints that use the same set of variables."""
##        for constraint in constraints:
##            self.add_constraint(constraint, scope)
##            
##    def solution(self):
##        """Find and return a solution to the CSP. A solution is a dictionary 
##        mapping variable names to their respective values in the solution."""
##        domains = dict((v.name, v.domain) for v in self.variables.itervalues())
##        return self.solver.solution(domains, self.scope)
##        
##    def solutions(self):
##        """Find all solutions to the problem. This may be a generator
##        or a list containing all complete solutions to the problem."""
##        domains = dict((v.name, v.domain) for v in self.variables.itervalues())
##        return self.solver.solutions(domains, self.scope)
##        
##    def apply(self, solution, model):
##        """Apply a set of variable assignments to the given model."""
##        for var, value in solution.iteritems():
##            self.variables[var].set(model, value)
##            
### ..............................................................................
### Constraint solver classes
### ..............................................................................
##class Enumerator(object):
##    """This "constraint solver" just enumerates all combinations of the variables,
##    without regarding any constraint."""
##    def solutions(self, domains, _):
##        return Enumerator.combinations(list(domains.iteritems()))
##        
##    @staticmethod
##    def combinations(domains):
##        if not domains:
##            yield {}
##        else:
##            var, domain = domains[0]
##            for value in domain:
##                for comb in Enumerator.combinations(domains[1:]):
##                    comb[var] = value
##                    yield comb
##
##class ConstraintSolver(object):
##    """Backtracing constraint solver."""
##    def __init__(self):
##        # a CSPManager is used for tracking available variables, constraints, 
##        # solution, available domains, scopes, active constraints, etc.
##        self.manager = None
##        self.stack = None # stack for backtracking
##        self.curr_var = None # variable currently being analyzed
##        self.curr_values = None # remaining values of the current variable
##        
##    def status(self):
##        self.manager.status()
##        print "Stack:"
##        for var, values in self.stack:
##            print "\t", var, values
##        print "Current variable:", self.curr_var, "-", self.curr_values
##        
##    def solution(self, domains, scopes):
##        """Return the first solution found."""
##        try:
##            return self.solutions(domains, scopes).next()
##        except StopIteration:
##            return None
##            
##    def solutions(self, domains, scopes):
##        """Return an iterator over all solutions."""
##        self.init(domains, scopes)
##        self.next_variable()
##        while self.curr_values:
##            value = self.curr_values.pop(0)#randint(0, len(self.curr_values)-1))
##            self.assign(self.curr_var, value, self.curr_values)
##            if not self.manager.check_consistency(assign_fnc=self.assign):
##                self.backtrack()
##            elif self.manager.unassigned():
##                self.next_variable()
##            else:
##                yield Namespace(self.manager.solution)
##                self.backtrack()
##                
##    # -------------
##    def init(self, domains, scopes):
##        self.stack = []
##        self.curr_var = None
##        self.curr_values = None
##        self.manager = CSPManager(domains, scopes)
##        self.manager.push_state()
##        self.manager.preprocess()
##        self.manager.reset_state()
##        
##    def assign(self, var, value, remaining=()):
##        self.stack.append((var, remaining))
##        self.manager.push_state()
##        self.manager.assign(var, value)
##        
##    def backtrack(self):
##        self.curr_values = None
##        while self.stack and not self.curr_values:
##            self.curr_var, self.curr_values = self.stack.pop()
##            self.manager.pop_state()
##            self.manager.unassign(self.curr_var)
##        if not self.curr_values and not self.stack:
##            raise StopIteration("end of search")
##            
##    def next_variable(self):
##        """Maximum Degree + Minimum Remaining Values variable picking heuristic.
##        This method chooses a variable among vars with maximum degree, and uses 
##        the minimum number of remaining values for tie breaking."""
##        self.curr_var = sorted(self.manager.varstore.variables, key=self.md_mrv)[0]
##        self.curr_values = self.manager.varstore.domain[self.curr_var][:]
##        
##    def md_mrv(self, var):
##        return -self.degree(var), self.domain_size(var)
##        
##    def degree(self, var):
##        return len(self.manager.constore.var_constraints[var])
##        
##    def domain_size(self, var):
##        return len(self.manager.varstore.domain[var])
##        
### ..............................................................................
### Variable and constraint store classes - used by the constraint solver to allow
### adding, removing, and temporary operations on the constraint and variable sets
### ..............................................................................
##class VariableStore(object):
##    def __init__(self, domains):
##        # domain -> a {var->domain} map
##        #   vars -> the unassigned variable set
##        self.domain = dict((var, domain.copy()) for var, domain in domains.iteritems())
##        self.variables = set(domains.iterkeys())
##        # Stacks of added and removed variables.
##        self.__added = []
##        self.__removed = []
##        
##    def __str__(self):
##        lines = [object.__repr__(self), "Variable domains:"]
##        for var, domain in sorted(self.domain.iteritems()):
##            lines.append("\t%s in %s" % (var, domain))
##        lines.append("Available variables:")
##        for var in sorted(self.variables):
##            lines.append("\t%s" % (var,))
##        return "\n".join(lines)
##        
##    def push_state(self):
##        self.__added.append([])
##        self.__removed.append([])
##        # Save the current state of the domains
##        for var in self.variables:
##            self.domain[var].push_state()
##            
##    def pop_state(self):
##        # Remove added variables and restore removed variables
##        added = self.__added.pop()
##        for var in added:
##            del self.domain[var]
##        self.variables.difference_update(added)
##        self.variables.update(self.__removed.pop())
##        # Restore the state of all domains
##        for var in self.variables:
##            self.domain[var].pop_state()
##            
##    def reset_state(self):
##        while self.__added:
##            self.pop_state()
##        for var in self.variables:
##            self.domain[var].reset_state()
##            
##    def add(self, var, domain):
##        self.variables.add(var)
##        self.domain[var] = domain.copy()
##        
##    def remove(self, var):
##        self.variables.remove(var)
##        return self.domain.pop(var)
##        
##    def temp_add(self, var, domain):
##        self.add(var, domain)
##        self.__added[-1].append(var)
##        
##    def temp_remove(self, var):
##        self.variables.remove(var)
##        self.__removed[-1].append(var)
##        
##    @contextmanager
##    def hiding(self, var):
##        self.variables.remove(var)
##        yield
##        self.variables.add(var)
##        
##class ConstraintStore(object):
##    def __init__(self, scopes, allvars):
##        #     constraints -> the set of available constraints
##        #           scope -> a {constraint->scope} map
##        # var_constraints -> a {var->constraints}  map
##        allvars = list(allvars)
##        self.scope = dict()
##        self.constraints = set()
##        self.var_constraints = dict((var, set()) for var in allvars)
##        for constraint, scope in scopes.iteritems():
##            if not scope:
##                scope = allvars
##            else:
##                scope = list(scope)
##            for var in scope:
##                self.var_constraints[var].add(constraint)
##            self.scope[constraint] = scope
##            self.constraints.add(constraint)
##        # Stacks of added and removed constraints
##        self.__added = []
##        self.__removed = []
##        
##    def __str__(self):
##        lines = [object.__repr__(self), "Constraint scopes:"]
##        for constraint, scope in self.scope.iteritems():
##            lines.append("\t%s using %s" % (constraint, scope))
##        lines.append("Variables:")
##        for var, constraints in self.var_constraints.iteritems():
##            lines.append("\t%s used by %s" % (var, constraints))
##        lines.append("Available constraints:")
##        for constraint in self.constraints:
##            lines.append(str(constraint))
##        return "\n".join(lines)
##        
##    def push_state(self):
##        self.__added.append([])
##        self.__removed.append([])
##        
##    def pop_state(self):
##        # Remove added constraints.
##        for constraint in self.__added.pop():
##            self.constraints.remove(constraint)
##            for var in self.scope.pop(constraint):
##                self.var_constraints[var].remove(constraint)
##        # Add removed constraints.
##        for constraint in self.__removed.pop():
##            self.constraints.add(constraint)
##            for var in self.scope[constraint]:
##                self.var_constraints[var].add(constraint)
##                
##    def reset_state(self):
##        while self.__added:
##            self.pop_state()
##            
##    def add(self, constraint, scope):
##        scope = list(scope)
##        self.scope[constraint] = scope
##        self.constraints.add(constraint)
##        for var in scope:
##            try:             self.var_constraints[var].add(constraint)
##            except KeyError: self.var_constraints[var] = set([constraint])
##            
##    def remove(self, constraint):
##        self.constraints.remove(constraint)
##        for var in self.scope.pop(constraint):
##            self.var_constraints[var].remove(constraint)
##            
##    def force_remove(self, constraint):
##        try:
##            self.constraints.remove(constraint)
##        except KeyError:
##            self.__removed[-1].remove(constraint)
##            del self.scope[constraint]
##        else:
##            for var in self.scope.pop(constraint):
##                self.var_constraints[var].remove(constraint)
##                
##    def remove_hidden(self):
##        for constraint in self.__removed[-1]:
##            self.scope.pop(constraint)
##        del self.__removed[-1][:]
##        
##    def temp_add(self, constraint, scope):
##        self.add(constraint, scope)
##        self.__added[-1].append(constraint)
##        
##    def temp_remove(self, constraint):
##        """This may be used for instance by the SomeInSetConstraint, which 
##        may become satisfied after the first variable in its scope belongs to
##        the given set. So, this constraint may be temporarily removed because 
##        it does not need to be evaluated again before backtracking."""
##        self.constraints.remove(constraint)
##        for var in self.scope[constraint]:
##            self.var_constraints[var].remove(constraint)
##        self.__removed[-1].append(constraint)
##        
##class CSPManager(object):
##    def __init__(self, domains, scopes):
##        self.varstore = VariableStore(domains)
##        self.constore = ConstraintStore(scopes, domains.iterkeys())
##        self.active_constraints = set()
##        self.touched_vars = set()
##        self.solution = {}
##        
##    def status(self):
##        print "Variable store:"
##        print self.varstore
##        print "Constraint store:"
##        print self.constore
##        print "Active constraints:"
##        print self.active_constraints
##        print "Current solution:"
##        print self.solution
##        
##    def push_state(self):
##        self.varstore.push_state()
##        self.constore.push_state()
##        self.active_constraints.clear()
##        
##    def pop_state(self):
##        self.varstore.pop_state()
##        self.constore.pop_state()
##        
##    def reset_state(self):
##        self.varstore.reset_state()
##        self.constore.reset_state()
##        self.active_constraints.clear()
##        self.solution.clear()
##        
##    # ..........................................................................
##    def scope(self, constraint):
##        return self.constore.scope[constraint]
##        
##    def scope_assigned(self, constraint):
##        return self.assigned().intersection(self.constore.scope[constraint])
##        
##    def scope_unassigned(self, constraint):
##        return self.unassigned().intersection(self.constore.scope[constraint])
##        
##    # ..........................................................................
##    def domain(self, var):
##        return self.varstore.domain[var]
##        
##    def domain_hide(self, var, value):
##        self.varstore.domain[var].hide(value)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    def domain_hide_ne(self, var, value):
##        self.varstore.domain[var].hide_ne(value)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    def domain_hide_gt(self, var, value):
##        self.varstore.domain[var].hide_gt(value)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    def domain_hide_ge(self, var, value):
##        self.varstore.domain[var].hide_ge(value)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    def domain_hide_lt(self, var, value):
##        self.varstore.domain[var].hide_lt(value)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    def domain_hide_le(self, var, value):
##        self.varstore.domain[var].hide_le(value)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    def domain_hide_in(self, var, values):
##        self.varstore.domain[var].hide_in(values)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    def domain_hide_notin(self, var, values):
##        self.varstore.domain[var].hide_notin(values)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        
##    # ..........................................................................
##    def constraint_available(self, constraint):
##        return constraint in self.constore.constraints
##        
##    def remove_constraint(self, constraint):
##        self.constore.remove(constraint)
##        
##    def force_remove_constraint(self, constraint):
##        self.constore.force_remove(constraint)
##        
##    def remove_hidden_constraints(self, constraint):
##        self.constore.remove_hidden()
##        
##    def hide_constraint(self, constraint):
##        if constraint in self.constore.constraints:
##            self.constore.temp_remove(constraint)
##            
##    def hide_variable(self, var):
##        self.varstore.temp_remove(var)
##        
##    def hiding_variable(self, var):
##        return self.varstore.hiding(var)
##        
##    def temp_constraint(self, constraint, scope):
##        self.constore.temp_add(constraint, scope)
##        
##    def temp_variable(self, variable, domain):
##        self.varstore.temp_add(variable, domain)
##        
##    # ..........................................................................
##    def assigned(self):
##        return set(self.solution.iterkeys())
##        
##    def unassigned(self):
##        return self.varstore.variables
##        
##    def constraints(self):
##        return self.constore.constraints
##        
##    # ..........................................................................
##    def preprocess(self):
##        self.active_constraints.update(self.constore.constraints)
##        while self.active_constraints:
##            constraint = self.active_constraints.pop()
##            if constraint in self.constore.constraints:
##                constraint.preprocess(self)
##                self.active_constraints.discard(constraint)
##        self.constore.remove_hidden()
##        
##    def check_consistency(self, assign_fnc=None):
##        if assign_fnc is None:
##            assign_fnc = self.assign
##        while self.active_constraints:
##            constraint = self.active_constraints.pop()
##            if constraint in self.constore.constraints:
##                assigned = constraint.eval(self.solution, self)
##                if assigned is None:
##                    self.active_constraints.clear()
##                    return False
##                for var, value in assigned:
##                    assign_fnc(var, value)
##                self.active_constraints.discard(constraint)
##        return True
##        
##    def assign(self, var, value):
##        self.varstore.temp_remove(var)
##        self.active_constraints.update(self.constore.var_constraints[var])
##        self.solution[var] = value
##        
##    def unassign(self, var):
##        del self.solution[var]
##        
### ..............................................................................
### Constraint classes
### ..............................................................................
##UNASSIGNED = State("unassigned")
##
##class Constraint(object):
##    def __repr__(self):
##        return "%s(%s)" % (self.__class__.__name__, self.repr())
##        
##    def info(self):
##        return ""
##        
##    def preprocess(self, manager):
##        """This method is called before starting to look for solutions,
##        and is used to prune domains with specific constraint logic when 
##        possible. For instance, any constraints with a single variable 
##        may be applied on all possible values and removed, since they 
##        may act on individual values even without further knowledge 
##        about other assignments."""
##        scope = manager.scope(self)
##        if len(scope) == 1:
##            var = scope[0]
##            domain = manager.domain(var)
##            with manager.hiding_variable(var):
##                for value in domain[:]:
##                    if self.eval({var: value}, manager) is None:
##                        domain.remove(value)
##            manager.hide_constraint(self)
##            
##    def eval(self, assigned, manager, forwardcheck=True):
##        """Return a boolean telling if the constraint is satisfiable or not."""
##        raise NotImplementedError()
##        
##    def forwardcheck(self, assigned, manager):
##        """Helper method for generic forward checking. Currently, this method 
##        acts only when there's a single unassigned variable."""
##        missing = manager.scope_unassigned(self)
##        if len(missing) == 1:
##            # Remove from the unassigned variable domain's all
##            # values which break this constraint.
##            var = missing.pop()
##            domain = manager.domain(var)
##            with manager.hiding_variable(var):
##                for value in domain[:]:
##                    assigned[var] = value
##                    if self.eval(assigned, manager, forwardcheck=False) is None:
##                        manager.domain_hide(var, value)
##            del assigned[var]
##            if len(domain) == 0:
##                return None
##            if len(domain) == 1:
##                return [(var, domain[0])]
##            else:
##                manager.hide_constraint(self)
##        return []
##        
##class FunctionConstraint(Constraint):
##    """Constraint which wraps a function defining the constraint logic."""
##    def __init__(self, func, require_all=True):
##        self.function = func
##        self.require_all = require_all
##        
##    def info(self):
##        return self.function.__name__
##        
##    def eval(self, assigned, manager, forwardcheck=True):
##        missing = manager.scope_unassigned(self)
##        if len(missing) == 1 and forwardcheck:
##            return self.forwardcheck(assigned, manager)
##        if len(missing) == 0 or not self.require_all:
##            if self.function(*[assigned[var] for var in manager.scope(self)]):
##                manager.hide_constraint(self)
##                return []
##            else:
##                return None
##        return []
##        
##class AllDifferentConstraint(Constraint):
##    def preprocess(self, manager):
##        scope = manager.scope(self)
##        values = set()
##        for var in scope:
##            values.update(manager.domain(var))
##            if len(values) > len(scope):
##                return
##        if len(values) < len(scope):
##            raise ValueError("insufficient values for alldifferent constraint")
##            
##    def eval(self, assigned, manager, forwardcheck=True):
##        scope_assigned = manager.scope_assigned(self)
##        seen_values = set(assigned[var] for var in scope_assigned)
##        if len(seen_values) < len(scope_assigned):
##            return None
##            
##        assignments = []
##        if forwardcheck:
##            for var in manager.scope_unassigned(self):
##                domain = manager.domain(var)
##                domain_seen = seen_values.intersection(domain)
##                if len(domain_seen) == len(domain):
##                    return None
##                if len(domain_seen) > 0:
##                    manager.domain_hide_in(var, domain_seen)
##                    if len(domain) == 1:
##                        assignments.append((var, domain[0]))
##        return assignments
##        
##class AllEqualConstraint(Constraint):
##    def preprocess(self, manager):
##        # Build the intersection of the domains of all variables in the constraint
##        # If the intersection is empty, the constraint is not satisfiable.
##        scope = manager.scope(self)
##        common = set(manager.domain(scope[0]))
##        for var in scope[1:]:
##            common.intersection_update(manager.domain(var))
##            if not common:
##                raise ValueError("empty domain intersection. "
##                                 "unsatisfiable allequal constraint")
##        # Reduce the domain of each variable to the common values.
##        for var in scope:
##            domain = manager.domain(var)
##            del domain[:]
##            domain.extend(common)
##            if domain.sortable():
##                domain.sort()
##                
##    def eval(self, assigned, manager, forwardcheck=True):
##        scope_assigned = manager.scope_assigned(self)
##        X = UNASSIGNED
##        # If some variable is assigned, check that all are assigned 
##        if scope_assigned:
##            scope_assigned = list(scope_assigned)
##            X = assigned[scope_assigned.pop()]
##            for var in scope_assigned:
##                if assigned[var] != X:
##                    return None
##                    
##        if forwardcheck:
##            if X is UNASSIGNED:
##                # Build the intersection of the domains of all variables in the constraint
##                # If the intersection is empty, the constraint is not satisfiable.
##                scope = manager.scope(self)
##                common = set(manager.domain(scope[0]))
##                for var in scope[1:]:
##                    common.intersection_update(manager.domain(var))
##                    if not common:
##                        raise ValueError("empty domain intersection. "
##                                         "unsatisfiable allequal constraint")
##                # Reduce the domain of each variable to the common values.
##                for var in scope:
##                    manager.domain_hide_notin(common)
##                    
##            else:
##                # If some variable was assigned, reduce the domains of all 
##                # other variables to the single admissible value.
##                assignments = []
##                for var in manager.scope_unassigned(self):
##                    domain = manager.domain(var)
##                    if X not in domain:
##                        return None
##                    if len(domain) > 1:
##                        manager.domain_hide_ne(var, X)
##                    assignments.append((var, X))
##                manager.hide_constraint(self)
##                return assignments
##        return []
##        
##class MaxSumConstraint(Constraint):
##    def __init__(self, maxsum, coefficients=None):
##        self.maxsum = maxsum
##        self.coefficients = coefficients
##        
##    def info(self):
##        return str(self.maxsum)
##        
##    def preprocess(self, manager):
##        scope = manager.scope(self)
##        if self.coefficients is None:
##            self.coefficients = [1.0] * len(scope)
##            
##        maxsum = self.maxsum
##        coefficients = self.coefficients
##        for var, mul in zip(scope, coefficients):
##            domain = manager.domain(var)
##            for value in domain[:]:
##                if value * mul > maxsum:
##                    domain.remove_ge(value)
##                    if not domain:
##                        raise ValueError("empty domain after preprocessing maxsum constraint")
##                    break
##                    
##    def eval(self, assigned, manager, forwardcheck=False):
##        if not manager.scope_assigned(self):
##            return []
##            
##        scope = manager.scope(self)
##        unassigned_vars = []
##        unassigned_coefficients = []
##        maxsum = self.maxsum
##        coefficients = self.coefficients
##        sum = 0
##        for var, mul in zip(scope, coefficients):
##            if var in assigned:
##                sum += assigned[var] * mul
##                if sum > maxsum:
##                    return None
##            else:
##                unassigned_vars.append(var)
##                unassigned_coefficients.append(mul)
##        
##        if forwardcheck:
##            if len(unassigned_vars) == 1:
##                var = unassigned_vars[0]
##                mul = unassigned_coefficients[0]
##                domain = manager.domain(var)
##                for value in domain[:]:
##                    if sum + mul * value > maxsum:
##                        domain.hide_ge(value)
##                        if not domain:
##                            return None
##                        break
##                manager.hide_constraint(self)
##                return []
##                
##            else:
##                for var, mul in zip(unassigned_vars, unassigned_coefficients):
##                    domain = manager.domain(var)
##                    for value in domain[:]:
##                        if sum + value * mul > maxsum:
##                            domain.hide_ge(value)
##                            if not domain:
##                                return None
##                            break
##                            
##        if unassigned_vars:
##            temp = MaxSumConstraint(self.maxsum - sum, unassigned_coefficients)
##            manager.hide_constraint(self)
##            manager.temp_constraint(temp, unassigned_vars)
##        return []
##        
##class ExactSumConstraint(Constraint):
##    def __init__(self, exactsum, coefficients=None):
##        self.exactsum = exactsum
##        self.coefficients = coefficients
##        
##    def preprocess(self, manager):
##        scope = manager.scope(self)
##        if self.coefficients is None:
##            self.coefficients = [1.0] * len(scope)
##        coefficients = self.coefficients
##        exactsum = self.exactsum
##            
##        Constraint.preprocess(self, manager)
##        for var, mul in zip(scope, coefficients):
##            domain = manager.domain(var)
##            for value in domain[:]:
##                if value * mul > exactsum:
##                    domain.remove(value)
##                    
##    def __call__(self, assigned, manager, forwardcheck=False):
##        coefficients = self.coefficients
##        exactsum = self.exactsum
##            
##        sum = 0.0
##        missing = False
##        for var, mul in zip(scope, coefficients):
##            if var in assigned:
##                sum += assigned[var] * mul
##            else:
##                missing = True
##        if sum > exactsum:
##            return None
##            
##        if forwardcheck and missing:
##            for variable, multiplier in zip(variables, multipliers):
##                if variable not in assignments:
##                    domain = domains[variable]
##                    for value in domain[:]:
##                        if sum + value * multiplier > exactsum:
##                            domain.hideValue(value)
##                    if not domain:
##                        return False
##        if missing:
##            return sum <= exactsum
##        else:
##            return sum == exactsum
##
##class MinSumConstraint(Constraint):
##    """
##    Constraint enforcing that values of given variables sum at least
##    to a given amount
##
##    Example:
##
##    >>> problem = Problem()
##    >>> problem.addVariables(["a", "b"], [1, 2])
##    >>> problem.addConstraint(MinSumConstraint(3))
##    >>> sorted(sorted(x.items()) for x in problem.getSolutions())
##    [[('a', 1), ('b', 2)], [('a', 2), ('b', 1)], [('a', 2), ('b', 2)]]
##    """
##
##    def __init__(self, minsum, multipliers=None):
##        """
##        @param minsum: Value to be considered as the minimum sum
##        @type  minsum: number
##        @param multipliers: If given, variable values will be multiplied by
##                            the given factors before being summed to be checked
##        @type  multipliers: sequence of numbers
##        """
##        self._minsum = minsum
##        self._multipliers = multipliers
##
##    def __call__(self, variables, domains, assignments, forwardcheck=False):
##        for variable in variables:
##            if variable not in assignments:
##                return True
##        else:
##            multipliers = self._multipliers
##            minsum = self._minsum
##            sum = 0
##            if multipliers:
##                for variable, multiplier in zip(variables, multipliers):
##                    sum += assignments[variable]*multiplier
##            else:
##                for variable in variables:
##                    sum += assignments[variable]
##            if type(sum) is float:
##                sum = round(sum, 10)
##            return sum >= minsum
##
##class InSetConstraint(Constraint):
##    """
##    Constraint enforcing that values of given variables are present in
##    the given set
##
##    Example:
##
##    >>> problem = Problem()
##    >>> problem.addVariables(["a", "b"], [1, 2])
##    >>> problem.addConstraint(InSetConstraint([1]))
##    >>> sorted(sorted(x.items()) for x in problem.getSolutions())
##    [[('a', 1), ('b', 1)]]
##    """
##
##    def __init__(self, set):
##        """
##        @param set: Set of allowed values
##        @type  set: set
##        """
##        self._set = set
##
##    def __call__(self, variables, domains, assignments, forwardcheck=False):
##        # preProcess() will remove it.
##        raise RuntimeError, "Can't happen"
##
##    def preProcess(self, variables, domains, constraints, vconstraints):
##        set = self._set
##        for variable in variables:
##            domain = domains[variable]
##            for value in domain[:]:
##                if value not in set:
##                    domain.remove(value)
##            vconstraints[variable].remove((self, variables))
##        constraints.remove((self, variables))
##
##class NotInSetConstraint(Constraint):
##    """
##    Constraint enforcing that values of given variables are not present in
##    the given set
##
##    Example:
##
##    >>> problem = Problem()
##    >>> problem.addVariables(["a", "b"], [1, 2])
##    >>> problem.addConstraint(NotInSetConstraint([1]))
##    >>> sorted(sorted(x.items()) for x in problem.getSolutions())
##    [[('a', 2), ('b', 2)]]
##    """#"""
##
##    def __init__(self, set):
##        """
##        @param set: Set of disallowed values
##        @type  set: set
##        """
##        self._set = set
##
##    def __call__(self, variables, domains, assignments, forwardcheck=False):
##        # preProcess() will remove it.
##        raise RuntimeError, "Can't happen"
##
##    def preProcess(self, variables, domains, constraints, vconstraints):
##        set = self._set
##        for variable in variables:
##            domain = domains[variable]
##            for value in domain[:]:
##                if value in set:
##                    domain.remove(value)
##            vconstraints[variable].remove((self, variables))
##        constraints.remove((self, variables))
##
##class SomeInSetConstraint(Constraint):
##    """
##    Constraint enforcing that at least some of the values of given
##    variables must be present in a given set
##
##    Example:
##
##    >>> problem = Problem()
##    >>> problem.addVariables(["a", "b"], [1, 2])
##    >>> problem.addConstraint(SomeInSetConstraint([1]))
##    >>> sorted(sorted(x.items()) for x in problem.getSolutions())
##    [[('a', 1), ('b', 1)], [('a', 1), ('b', 2)], [('a', 2), ('b', 1)]]
##    """#"""
##
##    def __init__(self, set, n=1, exact=False):
##        """
##        @param set: Set of values to be checked
##        @type  set: set
##        @param n: Minimum number of assigned values that should be present
##                  in set (default is 1)
##        @type  n: int
##        @param exact: Whether the number of assigned values which are
##                      present in set must be exactly C{n}
##        @type  exact: bool
##        """
##        self._set = set
##        self._n = n
##        self._exact = exact
##
##    def __call__(self, variables, domains, assignments, forwardcheck=False):
##        set = self._set
##        missing = 0
##        found = 0
##        for variable in variables:
##            if variable in assignments:
##                found += assignments[variable] in set
##            else:
##                missing += 1
##        if missing:
##            if self._exact:
##                if not (found <= self._n <= missing+found):
##                    return False
##            else:
##                if self._n > missing+found:
##                    return False
##            if forwardcheck and self._n-found == missing:
##                # All unassigned variables must be assigned to
##                # values in the set.
##                for variable in variables:
##                    if variable not in assignments:
##                        domain = domains[variable]
##                        for value in domain[:]:
##                            if value not in set:
##                                domain.hideValue(value)
##                        if not domain:
##                            return False
##        else:
##            if self._exact:
##                if found != self._n:
##                    return False
##            else:
##                if found < self._n:
##                    return False
##        return True
##
##class SomeNotInSetConstraint(Constraint):
##    """
##    Constraint enforcing that at least some of the values of given
##    variables must not be present in a given set
##
##    Example:
##
##    >>> problem = Problem()
##    >>> problem.addVariables(["a", "b"], [1, 2])
##    >>> problem.addConstraint(SomeNotInSetConstraint([1]))
##    >>> sorted(sorted(x.items()) for x in problem.getSolutions())
##    [[('a', 1), ('b', 2)], [('a', 2), ('b', 1)], [('a', 2), ('b', 2)]]
##    """#"""
##
##    def __init__(self, set, n=1, exact=False):
##        """
##        @param set: Set of values to be checked
##        @type  set: set
##        @param n: Minimum number of assigned values that should not be present
##                  in set (default is 1)
##        @type  n: int
##        @param exact: Whether the number of assigned values which are
##                      not present in set must be exactly C{n}
##        @type  exact: bool
##        """
##        self._set = set
##        self._n = n
##        self._exact = exact
##
##    def __call__(self, variables, domains, assignments, forwardcheck=False):
##        set = self._set
##        missing = 0
##        found = 0
##        for variable in variables:
##            if variable in assignments:
##                found += assignments[variable] not in set
##            else:
##                missing += 1
##        if missing:
##            if self._exact:
##                if not (found <= self._n <= missing+found):
##                    return False
##            else:
##                if self._n > missing+found:
##                    return False
##            if forwardcheck and self._n-found == missing:
##                # All unassigned variables must be assigned to
##                # values not in the set.
##                for variable in variables:
##                    if variable not in assignments:
##                        domain = domains[variable]
##                        for value in domain[:]:
##                            if value in set:
##                                domain.hideValue(value)
##                        if not domain:
##                            return False
##        else:
##            if self._exact:
##                if found != self._n:
##                    return False
##            else:
##                if found < self._n:
##                    return False
##        return True
##        
##
##constraint = Namespace(function=FunctionConstraint, 
##                       alldifferent=AllDifferentConstraint, 
##                       allequal=AllEqualConstraint, 
##                       maxsum=MaxSumConstraint, 
##                       exactsum=ExactSumConstraint, 
##                       minsum=MinSumConstraint, 
##                       inset=InSetConstraint, 
##                       notinset=NotInSetConstraint, 
##                       someinset=SomeInSetConstraint, 
##                       somenotinset=SomeNotInSetConstraint)
